//https://leetcode.cn/problems/construct-string-with-repeat-limit/description/?envType=daily-question&envId=2024-01-13


class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        int n = s.size();
        string ans;
        vector<int> vec(26, 0);

        for(const char& c : s) ++vec[c-'a'];

        int first = 25;
        while(first >= 0 && vec[first] == 0) --first;
        int second = first - 1;
        while(second >= 0 && vec[second] == 0) --second;

        while(second >= 0) {
            if(vec[first] <= repeatLimit) {
                ans.append(vec[first], (char)(first + 'a'));
                vec[first] = 0;
                first = second--;
                while(second >= 0 && vec[second] == 0) second--;
            } else {
                ans.append(repeatLimit, (char)(first + 'a'));
                vec[first] -= repeatLimit;
                ans += (char)(second + 'a');
                if(--vec[second] == 0) {
                    while(second >= 0 && vec[second] == 0) second--;
                    if(second < 0) break;
                }
            }
        }

        ans.append(std::min(vec[first], repeatLimit), (char)(first + 'a'));

        return ans;
    }
};